Find All Anagrams (Hash, Two-Pointer, Sliding Window)

15 Jun, 2021

Problem

Write a program that counts the number of substrings of S that are anagrams and T strings in S string. When identifying anagrams, case is sensitive. Substrings must be contiguous strings.

input

The first S string is entered on the first line, and the T string is entered on the second line
The length of S-string cannot exceed 10,000, and T-string is less than or equal to S-string

bacaAacba
abc

output

Outputs the number of substrings that become T strings and anagrams in S word.

Solution

O(nm): Using `Sort()`

function solution(s, t) {
	let answer = 0;

	// sorted arr2
	const arr2 = t.split('').sort();

	for (let i = 0; i < s.length - (t.length - 1); i++) {
		let arr1 = [];

		for (let j = 0; j < t.length; j++) arr1.push(s[i + j]);

		// sorted arr1
		const sortedArr1 = arr1.sort();

		// check validation
		let isValid = true;

		for (let k = 0; k < sortedArr1.length; k++) {
			if (sortedArr1[k] !== arr2[k]) isValid = false;
		}
		if (isValid) answer++;
	}

	return answer;
}

Use `Map().set()` & `Map().get()`, Two pointer Algo

function compareMaps(map1, map2) {
	if (map1.size !== map2.size) return false;

	for (let [key, val] of map1) {
		if (!map2.has(key) || map2.get(key) !== val) return false;
	}

	return true;
}

function solution(s, t) {
	let answer = 0,
		sH = new Map(),
		tH = new Map();

	/** map setting */

	for (let x of t) {
		if (tH.has(x)) tH.set(x, tH.get(x) + 1);
		else tH.set(x, 1);
	}

	let len = t.length - 1;

	for (let i = 0; i < len; i++) {
		if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
		else sH.set(s[i], 1);
	}

	/**  sliding */

	let lt = 0;

	for (let rt = len; rt < s.length; rt++) {
		if (sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt]) + 1);
		else sH.set(s[rt], 1);

		if (compareMaps(sH, tH)) answer++;

		// substract
		sH.set(s[lt], sH.get(s[lt]) - 1);
		if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
		lt++;
	}

	return answer;
}